package leetcode.editor.cn.q1_300.q100;

import java.util.*;

/**
 * 第二道自己做出来的动态规划
 *
 * @author qidi
 * @date 2022-01-14 15:30:28
 */
class Q0139_WordBreak {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean wordBreak(String s, List<String> wordDict) {
            Map<Integer, List<String>> map = new HashMap<>();
            int n = s.length();
            int maxLen = 0;
            int minLen = n;
            for (String w : wordDict) {
                int len = w.length();
                map.putIfAbsent(len, new ArrayList<>());
                map.get(len).add(w);
                maxLen = Math.max(maxLen, len);
                minLen = Math.min(minLen, len);
            }

            boolean[] dp = new boolean[n + 1];
            dp[0] = true;

            for (int i = 0; i <= n; i++) {
                for (int j = i - minLen; j >= i - maxLen && j >= 0; j--) {
                    int curLen = i - j;
                    if (map.containsKey(curLen) && map.get(curLen).contains(s.substring(j, i)) && dp[j]) {
                        dp[i] = true;
                        break;
                    }
                }
            }

            return dp[n];
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0139_WordBreak().new Solution();
        System.out.println(solution.wordBreak("catsandog", Arrays.asList("cats", "dog", "sand", "and", "cat")));
        System.out.println(solution.wordBreak("leetcode", Arrays.asList("leet", "code")));
        System.out.println(solution.wordBreak("applepenapple", Arrays.asList("apple", "pen")));
    }
}